package excise;

import java.util.Arrays;

/**
 * @author CoderXshuai
 * @date 2020/7/12/0012 0:22
 */

public class Test {
    // 快速排序
    public static void quickSort(int[] array) {
        // 调用快速排序的核心，传入left，right
        quickSortCore(array, 0, array.length - 1);
    }

    // 快速排序的核心，同样也是递归函数
    public static void quickSortCore(int[] array, int left, int right) {
        // 递归基准条件，left >= right 即表示数组只有1个或者0个元素。
        if (left >= right) {
            return;
        }
        // 根据轴分区
        int pivotIndex = partition(array, left, right);

        // 递归调用左侧和右侧数组分区
        quickSortCore(array, left, pivotIndex - 1);
        quickSortCore(array, pivotIndex + 1, right);
    }

    // 对数组进行分区，并返回当前轴所在的位置
    public static int partition(int[] array, int left, int right) {
        //目标值的下标
        int initRight = right;
        //目标值
        int aim = array[right];
        //右指针-1
        right--;
        //循环找到目标值的正确位置
        while (true) {
            //如果目标值大于左指针的值,而且左指针小于目标值的下标
            //之所以是小于目标值的下标而不是右指针的下标,考虑的是如果目标值比所有值大的情况
            while (array[left] <= aim && left < initRight) {
                left++;
            }
            //如果目标值小于右指针的下标,而且右指针小于左指针
            //如果目标值小于所有值,那么也是可以直接交换,具体你自己分析过就明白了
            while (array[right] >= aim && right > left) {
                right--;
            }
            //循环终止条件
            if (left >= right) {
                break;
            } else {
                //否则就交换左右指针的值
                swap(array, left, right);
            }
        }
        //交换当前左指针指向的值与目标值
        swap(array, initRight, left);
        return left;
    }

    public static void swap(int[] array, int leftIndex, int rightIndex) {
        int temp = array[leftIndex];
        array[leftIndex] = array[rightIndex];
        array[rightIndex] = temp;
    }

    public static void main(String[] args) {
        int[] array = {72, 77, 48, 17, 71, 2, 25, 97, 82, 5, 2, 18, 15, 57, 7, 48, 93, 47, 38, 74, 18, 93, 98, 41, 54, 4, 47, 4, 63, 76};
        // Arrays.toString 可以方便打印数组内容
//        int[] array = {1, 3, 9};
        System.out.println("raw: " + Arrays.toString(array));
        quickSort(array);
        System.out.println("result: " + Arrays.toString(array));
    }
}
